{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Smallest K-Length Subsequence With Occurrences of a Letter"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #greedy #string #monotonic-stack"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #贪心 #字符串 #单调栈"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: smallestSubsequence"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #含特定字母的最小子序列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串 <code>s</code> ，一个整数 <code>k</code> ，一个字母 <code>letter</code> 以及另一个整数 <code>repetition</code> 。</p>\n",
    "\n",
    "<p>返回 <code>s</code> 中长度为 <code>k</code> 且 <strong>字典序最小</strong> 的子序列，该子序列同时应满足字母 <code>letter</code> 出现<strong> 至少</strong> <code>repetition</code> 次。生成的测试用例满足 <code>letter</code> 在 <code>s</code> 中出现 <strong>至少</strong> <code>repetition</code> 次。</p>\n",
    "\n",
    "<p><strong>子序列</strong> 是由原字符串删除一些（或不删除）字符且不改变剩余字符顺序得到的剩余字符串。</p>\n",
    "\n",
    "<p>字符串 <code>a</code> 字典序比字符串 <code>b</code> 小的定义为：在 <code>a</code> 和 <code>b</code> 出现不同字符的第一个位置上，字符串 <code>a</code> 的字符在字母表中的顺序早于字符串 <code>b</code>&nbsp;的字符。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"leet\", k = 3, letter = \"e\", repetition = 1\n",
    "<strong>输出：</strong>\"eet\"\n",
    "<strong>解释：</strong>存在 4 个长度为 3 ，且满足字母 'e' 出现至少 1 次的子序列：\n",
    "- \"lee\"（\"<em><strong>lee</strong></em>t\"）\n",
    "- \"let\"（\"<em><strong>le</strong></em>e<em><strong>t</strong></em>\"）\n",
    "- \"let\"（\"<em><strong>l</strong></em>e<em><strong>et</strong></em>\"）\n",
    "- \"eet\"（\"l<em><strong>eet</strong></em>\"）\n",
    "其中字典序最小的子序列是 \"eet\" 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"example-2\" src=\"https://assets.leetcode.com/uploads/2021/09/13/smallest-k-length-subsequence.png\" style=\"width: 339px; height: 67px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"leetcode\", k = 4, letter = \"e\", repetition = 2\n",
    "<strong>输出：</strong>\"ecde\"\n",
    "<strong>解释：</strong>\"ecde\" 是长度为 4 且满足字母 \"e\" 出现至少 2 次的字典序最小的子序列。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"bb\", k = 2, letter = \"b\", repetition = 2\n",
    "<strong>输出：</strong>\"bb\"\n",
    "<strong>解释：</strong>\"bb\" 是唯一一个长度为 2 且满足字母 \"b\" 出现至少 2 次的子序列。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= repetition &lt;= k &lt;= s.length &lt;= 5 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>s</code> 由小写英文字母组成</li>\n",
    "\t<li><code>letter</code> 是一个小写英文字母，在 <code>s</code>&nbsp;中至少出现 <code>repetition</code> 次</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [smallest-k-length-subsequence-with-occurrences-of-a-letter](https://leetcode.cn/problems/smallest-k-length-subsequence-with-occurrences-of-a-letter/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [smallest-k-length-subsequence-with-occurrences-of-a-letter](https://leetcode.cn/problems/smallest-k-length-subsequence-with-occurrences-of-a-letter/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"leet\"\\n3\\n\"e\"\\n1', '\"leetcode\"\\n4\\n\"e\"\\n2', '\"bb\"\\n2\\n\"b\"\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str, k: int, letter: str, repetition: int) -> str:\n",
    "        st = []\n",
    "        n = len(s)\n",
    "        cnt = s.count(letter)\n",
    "        t = n - k\n",
    "        p = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            x = s[i]\n",
    "            while st and st[-1] > x and t > 0:\n",
    "                if st[-1] == letter:\n",
    "                    if repetition > p - 1 + cnt:\n",
    "                        break\n",
    "                    p -= 1\n",
    "\n",
    "                st.pop()\n",
    "                t -= 1\n",
    "\n",
    "            st.append(x)\n",
    "\n",
    "            if x == letter:\n",
    "                p += 1\n",
    "                cnt -= 1\n",
    "\n",
    "        while len(st) > k:\n",
    "            if st[-1] == letter:\n",
    "                p -= 1\n",
    "\n",
    "            st.pop()\n",
    "\n",
    "        for i in range(k - 1, -1, -1):\n",
    "            if p < repetition and st[i] != letter:\n",
    "                st[i] = letter\n",
    "                p += 1\n",
    "\n",
    "        return ''.join(st)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, a: str, k: int, l: str, r: int) -> str:\n",
    "        n = len(a)\n",
    "        m = len([j for j in a if j==l]) #至少r次\n",
    "        b = n-k\n",
    "        s = []\n",
    "        for j in a:\n",
    "            while s and (j<s[-1]) and b:\n",
    "                if s[-1]!=l:\n",
    "                    s.pop() \n",
    "                    b -= 1 \n",
    "                else:\n",
    "                    if m>r:\n",
    "                        s.pop()\n",
    "                        b-=1 \n",
    "                        m-=1 \n",
    "                    else:\n",
    "                        break \n",
    "            s.append(j) \n",
    "        c = []\n",
    "        while b:\n",
    "            t = s.pop()\n",
    "            if t!=l:\n",
    "                b-=1 \n",
    "            else:\n",
    "                if m>r:\n",
    "                    b-=1 \n",
    "                    m-=1 \n",
    "                else:\n",
    "                    c.append(t)\n",
    "        s += c \n",
    "        return ''.join(s)\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str, k: int, letter: str, repetition: int) -> str:\n",
    "        n = len(s)\n",
    "\n",
    "        cnt = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            if s[i] == letter: cnt += 1\n",
    "\n",
    "        \n",
    "        toErase = n - k\n",
    "\n",
    "        res = []\n",
    "        p = 0\n",
    "\n",
    "        for i in range(n):\n",
    "\n",
    "            while (toErase and res and s[i] < res[-1]):\n",
    "                if res[-1] == letter:\n",
    "\n",
    "                    if repetition > p - 1 + cnt:\n",
    "                        break\n",
    "                    p -= 1\n",
    "                res.pop()\n",
    "                toErase -= 1\n",
    "            \n",
    "            if s[i] == letter:\n",
    "                p += 1\n",
    "                cnt -= 1\n",
    "            res.append(s[i])\n",
    "        \n",
    "        while len(res) > k:\n",
    "            if res[-1] == letter:\n",
    "                p -= 1\n",
    "            res.pop()\n",
    "        \n",
    "        for i in range(k - 1, -1, -1):\n",
    "            if p < repetition and res[i] != letter:\n",
    "                res[i] = letter\n",
    "                p += 1\n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str, k: int, letter: str, repetition: int) -> str:\n",
    "\n",
    "        n = len(s)\n",
    "\n",
    "        cnt = 0\n",
    "\n",
    "        for i in range(n):\n",
    "            if s[i] == letter: cnt += 1\n",
    "\n",
    "        \n",
    "        toErase = n - k\n",
    "\n",
    "        res = []\n",
    "        p = 0\n",
    "\n",
    "        for i in range(n):\n",
    "\n",
    "            while (toErase and res and s[i] < res[-1]):\n",
    "                if res[-1] == letter:\n",
    "\n",
    "                    if repetition > p - 1 + cnt:\n",
    "                        break\n",
    "                    p -= 1\n",
    "                res.pop()\n",
    "                toErase -= 1\n",
    "            \n",
    "            if s[i] == letter:\n",
    "                p += 1\n",
    "                cnt -= 1\n",
    "            res.append(s[i])\n",
    "        \n",
    "        while len(res) > k:\n",
    "            if res[-1] == letter:\n",
    "                p -= 1\n",
    "            res.pop()\n",
    "        \n",
    "        for i in range(k - 1, -1, -1):\n",
    "            if p < repetition and res[i] != letter:\n",
    "                res[i] = letter\n",
    "                p += 1\n",
    "        return \"\".join(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str, k: int, letter: str, repetition: int) -> str:\n",
    "        # 单调栈去维护字典序最小的定长子序列，注意限制条件。\n",
    "        n = len(s)\n",
    "        cnt = Counter(s)\n",
    "        sta = []\n",
    "        inside_num = 0\n",
    "        for i,c in enumerate(s):\n",
    "            remain = n - i\n",
    "            if c == letter:\n",
    "                cnt[letter] -= 1\n",
    "            while sta and sta[-1]>c:\n",
    "                if len(sta) + remain == k:\n",
    "                    break\n",
    "                if sta[-1]!=letter:\n",
    "                    sta.pop(-1)\n",
    "                else:\n",
    "                    if inside_num + cnt[letter] > repetition:\n",
    "                        inside_num -= 1\n",
    "                        sta.pop(-1)\n",
    "                    else:\n",
    "                        break\n",
    "            if c == letter:\n",
    "                if len(sta)<k:\n",
    "                    sta.append(c)\n",
    "                    inside_num+=1\n",
    "                else:\n",
    "                    if inside_num + cnt[letter] + 1 == repetition:\n",
    "                        idx = len(sta) - 1\n",
    "                        while idx>=0 and sta[idx]==letter:\n",
    "                            idx -= 1\n",
    "                        sta[idx] = letter\n",
    "                        inside_num+=1\n",
    "            else: \n",
    "                if len(sta)<k:\n",
    "                    sta.append(c)\n",
    "        return \"\".join(sta)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str, k: int, letter: str, repetition: int) -> str:\n",
    "        n = len(s)\n",
    "        re = s.count(letter)\n",
    "        pre = 0\n",
    "        st = []\n",
    "        for i, ch in enumerate(s):\n",
    "            while st and st[-1] > ch and len(st) + n - i > k:\n",
    "                if st[-1] == letter:\n",
    "                    if pre - 1 + re < repetition:\n",
    "                        break\n",
    "                    pre -= 1\n",
    "                st.pop()\n",
    "            if ch == letter:\n",
    "                pre += 1\n",
    "                re -= 1\n",
    "            st.append(ch)\n",
    "\n",
    "        while len(st) > k:\n",
    "            if st[-1] == letter:\n",
    "                pre -= 1\n",
    "            st.pop()\n",
    "        \n",
    "        for i in range(k - 1, -1, -1):\n",
    "            if pre < repetition:\n",
    "                if st[i] != letter:\n",
    "                    st[i] = letter\n",
    "                    pre += 1\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        return ''.join(st)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str, k: int, letter: str, repetition: int) -> str:\n",
    "        # 求出经典的s中k长度的最小字典序子序列\n",
    "        n = len(s)\n",
    "        cnt = Counter(s)\n",
    "        sta = []\n",
    "        inside_num = 0\n",
    "        for i,c in enumerate(s):\n",
    "            remain = n - i  #剩下的字符数（包括当前的s[i]）\n",
    "            if c == letter:\n",
    "                cnt[letter] -= 1\n",
    "            while sta and sta[-1]>c:\n",
    "                if len(sta) + remain == k:\n",
    "                    break\n",
    "                if sta[-1]!=letter:\n",
    "                    sta.pop(-1)\n",
    "                else:\n",
    "                    if inside_num + cnt[letter] > repetition:\n",
    "                        inside_num -= 1\n",
    "                        sta.pop(-1)\n",
    "                    else:\n",
    "                        break\n",
    "            if c == letter:\n",
    "                if len(sta)<k:\n",
    "                    sta.append(c)\n",
    "                    inside_num+=1\n",
    "                else:\n",
    "                    if inside_num + cnt[letter] + 1 == repetition:\n",
    "                        idx = len(sta) - 1\n",
    "                        while idx>=0 and sta[idx]==letter:\n",
    "                            idx -= 1\n",
    "                        sta[idx] = letter\n",
    "                        inside_num+=1\n",
    "            else: \n",
    "                if len(sta)<k:\n",
    "                    sta.append(c)\n",
    "        return \"\".join(sta)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str, k: int, letter: str, repetition: int) -> str:\n",
    "        m,n = s.count(letter)-repetition,len(s)-k\n",
    "        v = 0\n",
    "        st = []\n",
    "        for c in s:\n",
    "            while st and st[-1]>c and n:\n",
    "                if st[-1]==letter:\n",
    "                    if m==0: break\n",
    "                    m -= 1\n",
    "                n -= 1\n",
    "                st.pop()\n",
    "            st.append(c)\n",
    "        st = st[:k]\n",
    "        cnt = st[:k].count(letter)\n",
    "        if cnt < repetition:\n",
    "            t = repetition-cnt\n",
    "            for i in range(k-1,-1,-1):\n",
    "                if st[i] != letter:\n",
    "                    st[i] = letter\n",
    "                    t -= 1\n",
    "                    if t == 0: break\n",
    "        return ''.join(st)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str, k: int, letter: str, repetition: int) -> str:\n",
    "\n",
    "        left = s.count(letter)\n",
    "        stack = []\n",
    "        t = len(s) - k\n",
    "        for ch in s:\n",
    "\n",
    "            while t and stack and ch < stack[-1]:\n",
    "                if stack[-1] == letter:\n",
    "                    if left - 1 < repetition:\n",
    "                        break\n",
    "                    stack.pop()\n",
    "                    left -= 1\n",
    "                    t -= 1\n",
    "                else:\n",
    "                    stack.pop()\n",
    "                    t -= 1\n",
    "            \n",
    "            stack.append(ch)\n",
    "        # print(stack)\n",
    "        stack = stack[:k]\n",
    "        c = stack.count(letter)\n",
    "        if c < repetition:\n",
    "            for j in range(k - 1, -1, -1):\n",
    "                if stack[j] != letter:\n",
    "                    stack[j] = letter\n",
    "                    c += 1\n",
    "                    if c >= repetition:\n",
    "                        break\n",
    "        return ''.join(stack)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str, k: int, letter: str, repetition: int) -> str:\n",
    "        n = len(s)\n",
    "        nCounter = Counter(s)\n",
    "        remaing = n\n",
    "        \n",
    "        stack = []\n",
    "        for s_i in s:\n",
    "            while stack and remaing > k and stack[-1] > s_i and \\\n",
    "                (  (stack[-1]!=letter) or (nCounter[stack[-1]] > repetition)):\n",
    "                nCounter[stack.pop()] -= 1\n",
    "                remaing -= 1\n",
    "            stack.append(s_i)\n",
    "        print(stack)\n",
    "        \n",
    "        # 如果 前k个里面 letter 数目不够，就从后向前删除 非 letter的，删一个在最后补一个letter\n",
    "        stack_k = stack[:k]\n",
    "        cur_n_letter = Counter(stack_k)[letter]\n",
    "        i = k-1\n",
    "        while cur_n_letter < repetition:\n",
    "            while stack_k[i] == letter:\n",
    "                i -= 1\n",
    "            stack_k.pop(i)\n",
    "            i -= 1\n",
    "            stack_k.append(letter)\n",
    "            cur_n_letter += 1\n",
    "        print(stack_k)\n",
    "\n",
    "        return(''.join(stack_k))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str, k: int, letter: str, repetition: int) -> str:\n",
    "        n = len(s)\n",
    "        ls = [i for i, ch in enumerate(s) if ch == letter]\n",
    "        q = deque()\n",
    "        res = []\n",
    "        for i, ch in enumerate(s):\n",
    "            while q and s[q[-1]] > ch:\n",
    "                q.pop()\n",
    "            q.append(i)\n",
    "            \n",
    "            while n - i == k or (repetition > 0 and i == ls[-repetition]):\n",
    "                j = q.popleft()\n",
    "                if k > 0 and (k > repetition or s[j] == letter):\n",
    "                    res.append(s[j])\n",
    "                    k -= 1\n",
    "                    repetition -= (res[-1] == letter)\n",
    "\n",
    "        return ''.join(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str, k: int, letter: str, repetition: int) -> str:\n",
    "        ct = 0\n",
    "        pres = [0]\n",
    "        for l in s:\n",
    "            if l == letter:\n",
    "                pres.append(pres[-1] + 1)\n",
    "            else:\n",
    "                pres.append(pres[-1])\n",
    "        st = []\n",
    "        n = len(s)\n",
    "        for i,l in enumerate(s):\n",
    "\n",
    "            while st and l < st[-1] and ct - [0,1][st[-1] == letter] + pres[-1] - pres[i] >= repetition and len(st) - 1 + n - i >= k:\n",
    "                ct -= [0,1][st.pop() == letter]\n",
    "            st.append(l)\n",
    "            ct += [0,1][l == letter]\n",
    "        \n",
    "        q = deque()\n",
    "        while len(st) + len(q) > k:\n",
    "            top = st[-1]\n",
    "            if top == letter:\n",
    "                st.pop()\n",
    "                if ct > repetition:\n",
    "                    ct -= 1\n",
    "                else:\n",
    "                    q.appendleft(top)\n",
    "            else:\n",
    "                st.pop()\n",
    "        st.extend(list(q))\n",
    "        return \"\".join(st)\n",
    "        \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str, k: int, letter: str, repetition: int) -> str:\n",
    "        n = len(s)\n",
    "        ls = [i for i, ch in enumerate(s) if ch == letter]\n",
    "        q = deque()\n",
    "        res = []\n",
    "        for i, ch in enumerate(s):\n",
    "            while q and s[q[-1]] > ch:\n",
    "                q.pop()\n",
    "            q.append(i)\n",
    "            \n",
    "            while n-i == k or (repetition > 0 and i == ls[-repetition]):\n",
    "                j = q.popleft()\n",
    "                if k > 0 and (k > repetition or s[j] == letter):\n",
    "                    # print(i,s[j])\n",
    "                    res.append(s[j])\n",
    "                    k -= 1\n",
    "                    repetition -= (res[-1] == letter)\n",
    "\n",
    "        return ''.join(res)\n",
    "\n",
    "            \n",
    "                \n",
    "            \n",
    "\n",
    "            \n",
    "        \n",
    "\n",
    "        \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from typing import List, Tuple  \n",
    "from collections import deque, Counter  \n",
    "from queue import PriorityQueue  \n",
    "import math  \n",
    "from functools import lru_cache  \n",
    "from sortedcontainers import SortedDict  \n",
    "import random  \n",
    "import copy  \n",
    "import sys  \n",
    "sys.setrecursionlimit(999999999)  \n",
    "  \n",
    "# 单调栈获取长度为k的最小子序列(不要求连续), 要求至少包含rep 个 letter\n",
    "def min_sequence_with_letter(s: List, k, letter, rep):  \n",
    "    n = len(s)  \n",
    "    if k > n:  \n",
    "        return None  \n",
    "    if k == n:  \n",
    "        return list(s)  \n",
    "  \n",
    "    A = [0] * n  \n",
    "    A[-1] = 0 if s[-1] != letter else 1  \n",
    "    for i in range(n-2, -1, -1):  \n",
    "        A[i] = A[i+1]  \n",
    "        if s[i] == letter:  \n",
    "            A[i] += 1  \n",
    "  \n",
    "    letter_cnt = 0      # stack中已经有的letter计数  \n",
    "  \n",
    "    stack = [0] * k  \n",
    "    s_idx = 0  \n",
    "    for idx, v in enumerate(s):  \n",
    "        # 将栈中偏大的数值淘汰掉, 淘汰的前提是淘汰完之后字符总数还能凑够K个，且letter个数还能凑够rep个  \n",
    "        while True:  \n",
    "            if s_idx > 0:  \n",
    "                cnt = letter_cnt if stack[s_idx-1] != letter else letter_cnt - 1  \n",
    "            else:  \n",
    "                cnt = 0  \n",
    "  \n",
    "            if s_idx > 0 and v < stack[s_idx-1] and (n - idx - 1) + s_idx >= k and cnt + A[idx] >= rep:  \n",
    "                pop_v = stack[s_idx-1]  \n",
    "                s_idx -= 1  \n",
    "                if pop_v == letter:  \n",
    "                    letter_cnt -= 1  \n",
    "            else:  \n",
    "                break  \n",
    "  \n",
    "        # 将栈里面多占了letter的位置的非letter数值淘汰掉  \n",
    "        if v == letter:  \n",
    "            while stack[s_idx-1] != letter and k - s_idx + letter_cnt < rep:  \n",
    "                s_idx -= 1  \n",
    "  \n",
    "        if s_idx < k:  \n",
    "            stack[s_idx] = v  \n",
    "            s_idx += 1  \n",
    "  \n",
    "            if v == letter:  \n",
    "                letter_cnt += 1  \n",
    "  \n",
    "    return stack  \n",
    "  \n",
    "class Solution:  \n",
    "    def smallestSubsequence(self, s: str, k: int, letter: str, repetition: int) -> str:  \n",
    "        return ''.join(min_sequence_with_letter(s, k, letter, repetition))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from typing import List, Tuple\n",
    "from collections import deque, Counter\n",
    "from queue import PriorityQueue\n",
    "import math\n",
    "from functools import lru_cache\n",
    "from sortedcontainers import SortedDict\n",
    "import random\n",
    "import copy\n",
    "import sys\n",
    "\n",
    "sys.setrecursionlimit(999999999)\n",
    "\n",
    "\n",
    "# 单调栈获取长度为k的最小子序列(不要求连续), 要求至少包含rep 个 letter\n",
    "def min_sequence_with_letter(s: List, k, letter, rep):\n",
    "    n = len(s)\n",
    "    if k > n:\n",
    "        return None\n",
    "    if k == n:\n",
    "        return list(s)\n",
    "\n",
    "    A = [0] * n\n",
    "    A[-1] = 0 if s[-1] != letter else 1\n",
    "    for i in range(n - 2, -1, -1):\n",
    "        A[i] = A[i + 1]\n",
    "        if s[i] == letter:\n",
    "            A[i] += 1\n",
    "\n",
    "    letter_cnt = 0  # stack中已经有的letter计数\n",
    "\n",
    "    stack = [0] * k\n",
    "    s_idx = 0\n",
    "    for idx, v in enumerate(s):\n",
    "        # 将栈中偏大的数值淘汰掉, 淘汰的前提是淘汰完之后字符总数还能凑够K个，且letter个数还能凑够rep个\n",
    "        while True:\n",
    "            if s_idx > 0:\n",
    "                cnt = letter_cnt if stack[s_idx - 1] != letter else letter_cnt - 1\n",
    "            else:\n",
    "                cnt = 0\n",
    "\n",
    "            if s_idx > 0 and v < stack[s_idx - 1] and (n - idx - 1) + s_idx >= k and cnt + A[idx] >= rep:\n",
    "                pop_v = stack[s_idx - 1]\n",
    "                s_idx -= 1\n",
    "                if pop_v == letter:\n",
    "                    letter_cnt -= 1\n",
    "            else:\n",
    "                break\n",
    "\n",
    "        # # 将栈里面多占了letter的位置的非letter数值淘汰掉\n",
    "        # if v == letter:\n",
    "        #     while stack[s_idx - 1] != letter and k - s_idx + letter_cnt < rep:\n",
    "        #         s_idx -= 1\n",
    "\n",
    "        t = 1 if v == letter else 0\n",
    "\n",
    "        if s_idx < k and (letter_cnt + t + (k-s_idx-1) >= rep):\n",
    "            stack[s_idx] = v\n",
    "            s_idx += 1\n",
    "\n",
    "            if v == letter:\n",
    "                letter_cnt += 1\n",
    "\n",
    "    return stack\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str, k: int, letter: str, repetition: int) -> str:\n",
    "        return ''.join(min_sequence_with_letter(s, k, letter, repetition))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def smallestSubsequence(self, s: str, k: int, letter: str, repetition: int) -> str:\r\n",
    "        n = len(s)\r\n",
    "\r\n",
    "        #----后缀，右侧出现指定字母的次数\r\n",
    "        suffix_cnt = [0 for _ in range(n)]\r\n",
    "        acc = 0\r\n",
    "        for i in range(n - 1, -1, -1):\r\n",
    "            acc += (s[i] == letter)\r\n",
    "            suffix_cnt[i] = acc\r\n",
    "        \r\n",
    "        stk = []\r\n",
    "        x = 0           #letter在res中已经出现的次数\r\n",
    "        for i in range(0, n):\r\n",
    "            y = x       #因为可能会操作，操作过程中letter在res中出现的次数\r\n",
    "            #----弹栈\r\n",
    "            while stk != [] and len(stk) + (n - i - 1) >= k and s[i] < stk[-1]:\r\n",
    "                if stk[-1] == letter:\r\n",
    "                    y -= 1\r\n",
    "                if y + suffix_cnt[i] < repetition:\r\n",
    "                    break\r\n",
    "                #--正式删\r\n",
    "                stk.pop(-1)\r\n",
    "                x = y\r\n",
    "\r\n",
    "            #----压栈\r\n",
    "            if len(stk) < k:\r\n",
    "                if s[i] == letter or k - len(stk) > repetition - x:\r\n",
    "                    stk.append(s[i])\r\n",
    "                    if s[i] == letter:\r\n",
    "                        x += 1\r\n",
    "        \r\n",
    "        return ''.join(stk)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def smallestSubsequence(self, s: str, k: int, letter: str, repetition: int) -> str:\n",
    "        n = len(s)\n",
    "        suffix_cnt = [0 for _ in range(n)]\n",
    "        acc = 0\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            acc += (s[i] == letter)\n",
    "            suffix_cnt[i] = acc\n",
    "        stk = []\n",
    "        x = 0\n",
    "        for i in range(0, n):\n",
    "            y = x\n",
    "            while stk != [] and len(stk) + (n - i - 1) >= k and s[i] < stk[-1]:\n",
    "                if stk[-1] == letter:\n",
    "                    y -= 1\n",
    "                if y + suffix_cnt[i] < repetition:\n",
    "                    break\n",
    "                stk.pop(-1)\n",
    "                x = y\n",
    "            if len(stk) < k:\n",
    "                if s[i] == letter or k - len(stk) > repetition - x:\n",
    "                    stk.append(s[i])\n",
    "                    if s[i] == letter:\n",
    "                        x += 1\n",
    "        return ''.join(stk)\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
